package DataStructure.peixu;

public class Merge {

    //辅助数组
    private static Comparable[] assist;


    //对元素进行排序
    public static void sort(Comparable[] a){
        //1.初始化辅助数组assist
        assist = new Comparable[a.length];
        //2.定义一个lo变量和一个hi变量，分别记录数据中最小的索引和最大的索引
        int lo=0;
        int hi=a.length-1;
        //3.调用sort重载方法完成数组从lo到hi的排序
        sort(a,lo,hi);
    }


    //对数组a中从lo到hi元素进行排序
    private static void sort(Comparable[] a,int lo,int hi){
        //做安全性校验
        if(lo>=hi){
            return;
        }
        //对lo到hi之间的数据分为两组
        int mid=lo+(hi-lo)/2;

        //分别对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        //在吧两组数据进行归并
        merge(a,lo,mid,hi);
    }


    //比较两元素的大小
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }

    //交换位置
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    //对两组数据进行归并
    private static void merge(Comparable[] a,int lo,int mid,int hi){
        //定义三个指针
        int i=lo;
        int p1=lo;
        int p2=mid+1;
        //对指针进行遍历移动p1和p2,比较对应索引处的值，找出小的放到辅助数组中
        while (p1<=mid && p2<=hi){
            //比较对应处的值
            if(less(a[p1],a[p2])){//小于的话返回真值，将小的数据放入辅助数组中
                assist[i++]=a[p1++];
            }else {
                assist[i++]=a[p2++];
            }
        }
        //遍历，如果p1的指针没有走完，那么顺序移动p1，把对应的值放到数组对应的索引处
        while (p1<=mid){
            assist[i++]=a[p1++];
        }
        //遍历，如果p2的指针没有走完，那么顺序移动p2，把对应的值放到数组对应的索引处
        while (p2<=hi){
            assist[i++]=a[p2++];
        }
        //把辅助数组中的元素拷贝到原数组中
        for (int index = lo; index <=hi; index++) {
            a[index]=assist[index];
        }
    }
}
